// 最长递增子序列的意思是
// 比如 [2,5,4,8,11,6], 它求出来的的就应该是 [2,4,8,11] (从左往右, 可以跳过, 但是不能往回走

// [1,8,5,3,4,9,7,6,2] 就是 1349 或 1347 或 1346
// 采用算法：贪心 + 二分查找
// 在查找中如果当前的比最后一个大,直接插入
// 如果当前这个比最后一个小,采用二分查找的方式,找到已经排好的列表,找到比当前数大的那第一项将其替换掉

// 1
// 1 8
// 1 5
// 1 3
// 1 3 4
// 1 3 4 9
// 1 3 4 7
// 1 3 4 6
// 1 2 4 6 // ←这样找出来的结果不对 但个数一定是对的 比如这里最长连续的个数一定是四个

// [2,3,1,5,6,8,7,9,4]
//
// 2
// 2 3
// 1 3
// 1 3 5
// 1 3 5 6
// 1 3 5 6 8
// 1 3 5 6 7
// 1 3 5 6 7 9
// 1 3 4 6 7 9


// getSequence 返回的是数组 数组成员的值 是找到的参数数组数组成员的索引

/** 1.  */
/*function getSequence(arr) {
  const len = arr.length;
  const result = [0]; //不论怎样 第一项肯定是要取的

  for (let i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) { // 我们vue3.x中的 newIndexToOldMapIndex 数组里的0是有特殊含义的 故不需要对其进行处理
      const resultLastIndex = result[result.length - 1]
      if (arr[resultLastIndex] < arrI) {
        result.push(i);
        continue
      }
    }
  }

  return result
}
console.log(getSequence([1,2,3,4,5,0])) //[ 0, 1, 2, 3, 4 ]
console.log(getSequence([1,2,0,3,4,5])) //[ 0, 1, 3, 4, 5 ]*/

/** 2. 整合二分查找*/

/*function getSequence(arr) {
  const len = arr.length;
  const result = [0]; //不论怎样 第一项肯定是要取的

  let start,
    end,
    middle

  for (let i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) { // 我们vue3.x中的 newIndexToOldMapIndex 数组里的0是有特殊含义的 故不需要对其进行处理
      const resultLastIndex = result[result.length - 1]
      if (arrI > arr[resultLastIndex]) {
        result.push(i);
        continue
      }

      start = 0;
      end = result.length -1;

      //找到结果集中 比当前这一项大的第一项
      //[1,8,5]
      while (start < end) {
        middle = ((start + end) / 2) | 0/!*向下取整*!/;
        if (arrI > arr[result[middle]]) {
          start = middle + 1;
        } else {
          end = middle;
        }
      }
      if (arrI < arr[result[start]]) {
        result[start] = i;
      }
    }
  }

  return result
}
console.log(getSequence([1,8,5,3,4,9,7,6,2])); //[ 0, 8, 4, 7 ] 即对应 1246, 但我们期望拿到的是1349或1347或1346 的索引位置 而不是 1246的
console.log(getSequence([2,3,1,5,6,7,9,4])); //[ 2, 1, 7, 4, 5, 6 ]
/!** ↑ 此时结果的长度是对的 但值是不对的*!/*/


/** 3. 无论换不换掉 先把前面那个人的位置索引记住
 *     查看：最长递增子序列.png*/
// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr) {
  const len = arr.length;
  const result = [0]; //不论怎样 第一项肯定是要取的
  const p = arr.slice(0); //里面的内容无所谓 用来存放索引

  let start,
    end,
    middle

  for (let i = 0; i < len; i++) {
    const arrI = arr[i];
    if (arrI !== 0) { // 我们vue3.x中的 newIndexToOldMapIndex 数组里的0是有特殊含义的 故不需要对其进行处理
      const resultLastIndex = result[result.length - 1]
      if (arrI > arr[resultLastIndex]) {
        p[i] = resultLastIndex;
        result.push(i);
        continue
      }

      start = 0;
      end = result.length - 1;

      //找到结果集中 比当前这一项大的第一项
      //[1,8,5]
      while (start < end) {
        middle = ((start + end) / 2) | 0/*向下取整*/;
        if (arrI > arr[result[middle]]) {
          start = middle + 1;
        } else {
          end = middle;
        }
      }
      if (arrI < arr[result[start]]) {
        if (start > 0) {
          p[i] = result[start - 1]; //记住当前的前一个人是谁
        }
        result[start] = i; //如果找到那个人 比他大才会替换
      }
    }
  }

  start = result.length;
  end = result[start - 1];
  while (start-- > 0) { //根据前驱节点一个个向前查找
    result[start] = end;
    end = p[end];
  }

  return result
}

console.log(getSequence([1, 8, 5, 3, 4, 9, 7, 6, 2])); //[ 0, 3, 4, 7 ]
console.log(getSequence([2, 3, 1, 5, 6, 7, 9, 4])); //[ 0, 1, 3, 4, 5, 6 ]

